// Copyright (c) 2012 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "leveldb/filter_policy.h"

#include "leveldb/slice.h"
#include "util/hash.h"

namespace leveldb {

    namespace {
        static uint32_t BloomHash(const Slice &key) {
            return Hash(key.data(), key.size(), 0xbc9f1d34);
        }

        class BloomFilterPolicy : public FilterPolicy {
        private:
            size_t bits_per_key_;   // 每个键采用多少个比特位记录
            size_t k_;              // 哈希函数的个数

        public:
            explicit BloomFilterPolicy(int bits_per_key)
                    : bits_per_key_(bits_per_key) {
                // We intentionally round down to reduce probing cost a little bit
                k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
                if (k_ < 1) k_ = 1;
                if (k_ > 30) k_ = 30;
            }

            virtual const char *Name() const {
                return "leveldb.BuiltinBloomFilter2";
            }

            // 采用批量的方式建立一个过滤器，
            // 传入 keys[], keys.size(), 以及一个字符串用于存放过滤器的比特位
            // 具体实现是在 dst 的基础上往后追加，dst 原来的内容存放的是其他键值对的过滤信息
            virtual void CreateFilter(const Slice *keys, int n, std::string *dst) const {
                // Compute bloom filter size (in both bits and bytes)
                size_t bits = n * bits_per_key_;

                // For small n, we can see a very high false positive rate.  Fix it
                // by enforcing a minimum bloom filter length.
                if (bits < 64) bits = 64;

                size_t bytes = (bits + 7) / 8;
                bits = bytes * 8;

                const size_t init_size = dst->size();
                dst->resize(init_size + bytes, 0);
                dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter
                char *array = &(*dst)[init_size];
                for (int i = 0; i < n; i++) {
                    // Use double-hashing to generate a sequence of hash values.
                    // See analysis in [Kirsch,Mitzenmacher 2006].
                    uint32_t h = BloomHash(keys[i]);
                    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
                    for (size_t j = 0; j < k_; j++) {
                        const uint32_t bitpos = h % bits;
                        array[bitpos / 8] |= (1 << (bitpos % 8));
                        h += delta;
                    }
                }
            }

            // 这个函数较为简单，仅仅是给定一个 key 和一个 bloom_filter，
            // 返回 bloom_filter 是否存放了该 key
            virtual bool KeyMayMatch(const Slice &key, const Slice &bloom_filter) const {
                const size_t len = bloom_filter.size();
                if (len < 2) return false;

                const char *array = bloom_filter.data();
                const size_t bits = (len - 1) * 8;

                // Use the encoded k so that we can read filters generated by
                // bloom filters created using different parameters.
                const size_t k = array[len - 1];
                if (k > 30) {
                    // Reserved for potentially new encodings for short bloom filters.
                    // Consider it a match.
                    return true;
                }

                uint32_t h = BloomHash(key);
                const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
                for (size_t j = 0; j < k; j++) {
                    const uint32_t bitpos = h % bits;
                    if ((array[bitpos / 8] & (1 << (bitpos % 8))) == 0) return false;
                    h += delta;
                }
                return true;
            }
        };
    }


    const FilterPolicy *NewBloomFilterPolicy(int bits_per_key) {
        return new BloomFilterPolicy(bits_per_key);
    }

}  // namespace leveldb
